package q647

import "fmt"

var cache map[string]bool

func countSubstrings(s string) int {

	var total int
	len := len(s)
	cache = map[string]bool{}

	for left := 0; left < len; left++ {
		for right := left; right < len; right++ {
			if isPalindrome(&s, left, right) {
				total++
			}
		}
	}
	return total
}

func isPalindrome(s *string, left, right int) (res bool) {
	sub := (*s)[left : right+1]
	isCalc, ok := cache[sub]
	if ok {
		return isCalc
	}
	defer func() {
		cache[sub] = res
		if res {
			D(left, right)
		}
	}()

	if left > right {
		res = false
		return
	} else if left == right {
		res = true
		return
	}

	for {
		if left > right {
			break
		}
		if (*s)[left:left+1] != (*s)[right:right+1] {
			return false
		}
		left++
		right--
	}
	res = true
	return res
}

func D(left, right int) {
	return
	fmt.Printf("%d,%d\n", left, right)
}
